/**
 * 地上有一个m行和n列的方格。
 * 一个机器人从坐标0,0的格子开始移动，
 * 每一次只能向左，右，上，下四个方向移动一格，
 * 但是不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格（35,37），
 * 因为3+5+3+7 = 18。但是，它不能进入方格（35,38），
 * 因为3+5+3+8 = 19。
 * 请问该机器人能够达到多少个格子？
 * Created by Administrator on 2017/2/16.
 */
public class Test1 {
    public static void main(String[] args) {
        System.out.println(movingCount(10, 1, 100));
    }

    public static int movingCount(int threshold, int rows, int cols) {
        int[] flag = new int[rows * cols];
        return movingCount(threshold, rows, cols, 0, 0, flag);
    }

    private static int movingCount(int threshold, int rows, int cols, int i, int j, int[] flag) {
        int index = cols * i + j;
        int count = 0;
        if (i >= 0 && j >= 0 && i < rows && j < cols &&
                getNumSum(i) + getNumSum(j) <= threshold && flag[index] != 1) {
            System.out.println(i + " " + j);
            flag[index] = 1;
            count++;
            //上
            count = 1 + movingCount(threshold, rows, cols, i, j - 1, flag) +
                    //右
                    movingCount(threshold, rows, cols, i + 1, j, flag) +
                    //下
                    movingCount(threshold, rows, cols, i, j + 1, flag) +
                    //左
                    movingCount(threshold, rows, cols, i - 1, j, flag);
        }
        return count;

    }

    private static int getNumSum(int cols) {
        int sum = 0;
        while (cols != 0) {
            sum = sum + (cols % 10);
            cols = cols / 10;
        }
        return sum;
    }


}
